<?php
/**
 * Zend Framework
 *
 * LICENSE
 *
 * This source file is subject to the new BSD license that is bundled
 * with this package in the file LICENSE.txt.
 * It is also available through the world-wide-web at this URL:
 * http://framework.zend.com/license/new-bsd
 * If you did not receive a copy of the license and are unable to
 * obtain it through the world-wide-web, please send an email
 * to license@zend.com so we can send you a copy immediately.
 *
 * @category   Zend
 * @package    Zend_Search_Lucene
 * @copyright  Copyright (c) 2005-2009 Zend Technologies USA Inc. (http://www.zend.com)
 * @license    http://framework.zend.com/license/new-bsd     New BSD License
 * @version    $Id: PriorityQueue.php 16541 2009-07-07 06:59:03Z bkarwin $
 */


/**
 * Abstract Priority Queue
 *
 * It implements a priority queue.
 * Please go to "Data Structures and Algorithms",
 * Aho, Hopcroft, and Ullman, Addison-Wesley, 1983 (corrected 1987 edition),
 * for implementation details.
 *
 * It provides O(log(N)) time of put/pop operations, where N is a size of queue
 *
 * @category   Zend
 * @package    Zend_Search_Lucene
 * @copyright  Copyright (c) 2005-2009 Zend Technologies USA Inc. (http://www.zend.com)
 * @license    http://framework.zend.com/license/new-bsd     New BSD License
 */
abstract class Zend_Search_Lucene_PriorityQueue
{
	/**
	 * Queue heap
	 *
	 * Heap contains balanced partial ordered binary tree represented in array
	 * [0] - top of the tree
	 * [1] - first child of [0]
	 * [2] - second child of [0]
	 * ...
	 * [2*n + 1] - first child of [n]
	 * [2*n + 2] - second child of [n]
	 *
	 * @var array
	 */
	private $_heap = array();


	/**
	 * Add element to the queue
	 *
	 * O(log(N)) time
	 *
	 * @param mixed $element
	 */
	public function put($element)
	{
		$nodeId   = count($this->_heap);
		$parentId = ($nodeId-1) >> 1;   // floor( ($nodeId-1)/2 )

		while ($nodeId != 0  &&  $this->_less($element, $this->_heap[$parentId])) {
			// Move parent node down
			$this->_heap[$nodeId] = $this->_heap[$parentId];

			// Move pointer to the next level of tree
			$nodeId   = $parentId;
			$parentId = ($nodeId-1) >> 1;   // floor( ($nodeId-1)/2 )
		}

		// Put new node into the tree
		$this->_heap[$nodeId] = $element;
	}


	/**
	 * Return least element of the queue
	 *
	 * Constant time
	 *
	 * @return mixed
	 */
	public function top()
	{
		if (count($this->_heap) == 0) {
			return null;
		}

		return $this->_heap[0];
	}


	/**
	 * Removes and return least element of the queue
	 *
	 * O(log(N)) time
	 *
	 * @return mixed
	 */
	public function pop()
	{
		if (count($this->_heap) == 0) {
			return null;
		}

		$top = $this->_heap[0];
		$lastId = count($this->_heap) - 1;

		/**
		 * Find appropriate position for last node
		 */
		$nodeId  = 0;     // Start from a top
		$childId = 1;     // First child

		// Choose smaller child
		if ($lastId > 2  &&  $this->_less($this->_heap[2], $this->_heap[1])) {
			$childId = 2;
		}

		while ($childId < $lastId  &&
		$this->_less($this->_heap[$childId], $this->_heap[$lastId])
		) {
			// Move child node up
			$this->_heap[$nodeId] = $this->_heap[$childId];

			$nodeId  = $childId;               // Go down
			$childId = ($nodeId << 1) + 1;     // First child

			// Choose smaller child
			if (($childId+1) < $lastId  &&
			$this->_less($this->_heap[$childId+1], $this->_heap[$childId])
			) {
				$childId++;
			}
		}

		// Move last element to the new position
		$this->_heap[$nodeId] = $this->_heap[$lastId];
		unset($this->_heap[$lastId]);

		return $top;
	}


	/**
	 * Clear queue
	 */
	public function clear()
	{
		$this->_heap = array();
	}


	/**
	 * Compare elements
	 *
	 * Returns true, if $el1 is less than $el2; else otherwise
	 *
	 * @param mixed $el1
	 * @param mixed $el2
	 * @return boolean
	 */
	abstract protected function _less($el1, $el2);
}

